import java.util.*;
public class TrulyMostPopular {
  private Map<String, String> map;
    
  public String[] trulyMostPopular(String[] names, String[] synonyms) {
      Map<String, Integer> count = new HashMap<>();
      map = new HashMap<>(); // 初始化map
      
      // 统计每个名字的出现次数
      for (String name : names) {
          String[] arr = name.split("\\(");
          String name1 = arr[0];
          int count1 = Integer.parseInt(arr[1].substring(0, arr[1].length() - 1));
          count.put(name1, count1);
      }
      
      // 并查集合并同义词
      for (String synonym : synonyms) {
          String[] temp = synonym.split(",");
          String x = temp[0].substring(1, temp[0].length());
          String y = temp[1].substring(0, temp[1].length() - 1);
          
          // 确保两个名字都在并查集中
          if (!map.containsKey(x)) map.put(x, x);
          if (!map.containsKey(y)) map.put(y, y);
          
          // 合并两个名字所在的集合
          union(x, y);
      }
      
      // 合并计数值，统计每个集合的总出现次数
      Map<String, Integer> resultCount = new HashMap<>();
      for (String name : count.keySet()) {
        if (!map.containsKey(name)) map.put(name, name);
          String root = find(name);
          resultCount.put(root, resultCount.getOrDefault(root, 0) + count.get(name));
      }
      
      // 生成结果数组
      String[] result = new String[resultCount.size()];
      int index = 0;
      for (Map.Entry<String, Integer> entry : resultCount.entrySet()) {
          result[index++] = entry.getKey() + "(" + entry.getValue() + ")";
      }
      
      return result;
  }
  
  // 查找根节点，包含路径压缩
  private String find(String x) {
      if (map.get(x).equals(x)) return x;
      // 路径压缩优化
      String root = find(map.get(x));
      map.put(x, root);
      return root;
  }
  
  // 合并两个元素所在的集合
  private void union(String x, String y) {
      String rootX = find(x);
      String rootY = find(y);
      
      if (!rootX.equals(rootY)) {
          // 将字典序小的作为根节点
          if (rootX.compareTo(rootY) > 0) {
              map.put(rootX, rootY);
          } else {
              map.put(rootY, rootX);
          }
      }
  }



  public static void main(String[] args) {
    String[] names = {"John(15)","Jon(12)","Chris(13)","Kris(4)","Christopher(19)"};
    String[] synonyms = {"(Jon,John)","(John,Johnny)","(Chris,Kris)","(Chris,Christopher)"};
    String[] res = new TrulyMostPopular().trulyMostPopular(names, synonyms);
    for (String s : res) {
      System.out.println(s);  
    }
  }
}
